package com.chj.gaoji.class15;

import java.util.Collections;
import java.util.PriorityQueue;

//https://leetcode-cn.com/problems/find-median-from-data-stream/solution/shuang-er-cha-dui-ji-qiao-xiang-jie-by-labuladong/
// https://leetcode-cn.com/problems/find-median-from-data-stream/
public class Code04_FindMedianFromDataStream {

	private PriorityQueue<Integer> maxHeap, minHeap;

	/**
	 * initialize your data structure here.
	 * 
	 * @return
	 */
	public void MedianFinder() {
		maxHeap = new PriorityQueue<>(Collections.reverseOrder());
		minHeap = new PriorityQueue<>();
	}

	public void addNum(int num) {
		maxHeap.offer(num);
		minHeap.offer(maxHeap.poll());
		// 如果不平衡则调整
		if (minHeap.size() > maxHeap.size()) {
			maxHeap.offer(minHeap.poll());
		}
	}

	public double findMedian() {
		if (maxHeap.size() == minHeap.size()) {
			return (maxHeap.peek() + minHeap.peek()) * 0.5;
		}
		return maxHeap.peek();
	}

//	作者：jerry_nju
//	链接：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/da-xiao-dui-si-lu-by-jerry_nju/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//	public class MedianFinder {
//
//		PriorityQueue<Integer> hi = new PriorityQueue<>();// 最小堆，根元素大于最大堆的根元素
//		PriorityQueue<Integer> lo = new PriorityQueue<>((x, y) -> y - x);// 最大堆，根元素小于最小堆的根元素
//
//		/** initialize your data structure here. */
//		public MedianFinder() {
//
//		}
//
//		public void addNum(int num) {
//			lo.add(num); // Add to max heap
//
//			hi.add(lo.peek()); // balancing step
//			lo.poll();
//
//			if (lo.size() < hi.size()) { // maintain size property
//				lo.add(hi.peek());
//				hi.poll();
//			}
//		}
//
//		public double findMedian() {
//			double ans = 0.0;
//			if (lo.size() > hi.size()) {
//				ans = (double) lo.peek();
//			} else {
//				ans = (lo.peek() + hi.peek()) * 0.5;
//			}
//			return ans;
//		}
//	}

//	作者：akian
//	链接：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/295-shu-ju-liu-de-zhong-wei-shu-by-akian/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//const (
//	// RED 红色
//	RED int = 10
//	// BLACK 黑色
//	BLACK int = 99
//)
//
//type RbData struct {
//	k int
//	v int
//}
//
//func NewRbData(k, v int) *RbData {
//	return &RbData{k: k, v: v}
//}
//
//type RbNode struct {
//	data     *RbData
//	color    int
//	parent   *RbNode
//	left     *RbNode
//	right    *RbNode
//	sizeLeft int
//}
//
//func NewRbNode(data *RbData, p, l, r *RbNode) *RbNode {
//	return &RbNode{data: data, parent: p, left: l, right: r, color: RED}
//}
//
//func NewRBBN(data *RbData, p, l, r *RbNode) *RbNode {
//	return &RbNode{data: data, parent: p, left: l, right: r, color: BLACK}
//}
//
//type DIndexRBTree struct {
//	root *RbNode
//	size int
//}
//
//func NewDIndexRBTree() *DIndexRBTree {
//	return &DIndexRBTree{}
//}
//
//func (this *DIndexRBTree) Search(k int) *RbData {
//	p := this.root
//
//	for p != nil {
//		if k < p.data.k {
//			p = p.left
//		} else if k > p.data.k {
//			p = p.right
//		} else {
//			return p.data
//		}
//	}
//	return nil
//}
//
//func (this *DIndexRBTree) IndexSearch(i int) *RbData {
//	p := this.root
//
//	for p != nil && p.sizeLeft != i {
//		if i < p.sizeLeft {
//			p = p.left
//		} else {
//			i -= (p.sizeLeft + 1)
//			p = p.right
//		}
//	}
//
//	if p == nil {
//		return nil
//	}
//	return p.data
//}
//
//func (this *DIndexRBTree) llRotate(py, v *RbNode) {
//	gy := py.parent
//
//	py.left = v.right
//	if v.right != nil {
//		v.right.parent = py
//	}
//
//	v.right = py
//	py.parent = v
//
//	py.sizeLeft -= (v.sizeLeft + 1)
//	v.parent = gy
//	if py == this.root {
//		v.parent = nil
//		this.root = v
//	} else {
//
//		if gy.left == py {
//			gy.left = v
//		} else {
//			gy.right = v
//		}
//	}
//
//}
//
//func (this *DIndexRBTree) lrRotate(py, v, w *RbNode) {
//	gy := py.parent
//	v.right = w.left
//	if w.left != nil {
//		w.left.parent = v
//	}
//
//	w.left = v
//	v.parent = w
//
//	py.left = w.right
//	if w.right != nil {
//		w.right.parent = py
//	}
//
//	w.right = py
//	py.parent = w
//
//	py.sizeLeft -= (v.sizeLeft + 1 + w.sizeLeft + 1)
//	w.sizeLeft += (v.sizeLeft + 1)
//
//	w.parent = gy
//	if py == this.root {
//		this.root = w
//		w.parent = nil
//	} else {
//		if gy.left == py {
//			gy.left = w
//		} else {
//			gy.right = w
//		}
//	}
//
//}
//
//func (this *DIndexRBTree) lrrRotate(py, v, w, x *RbNode) {
//	gy := py.parent
//
//	x.color = py.color
//	py.color = BLACK
//
//	w.right = x.left
//	if x.left != nil {
//		x.left.parent = w
//	}
//
//	x.left = v
//	v.parent = x
//
//	py.left = x.right
//	if x.right != nil {
//		x.right.parent = py
//	}
//
//	x.right = py
//	py.parent = x
//
//	py.sizeLeft -= (x.sizeLeft + w.sizeLeft + v.sizeLeft + 3)
//	x.sizeLeft += (v.sizeLeft + w.sizeLeft + 2)
//	x.parent = gy
//
//	if py == this.root {
//		this.root = x
//		x.parent = nil
//	} else {
//		if gy.left == py {
//			gy.left = x
//		} else {
//			gy.right = x
//		}
//	}
//
//}
//
//func (this *DIndexRBTree) rrRotate(py, v *RbNode) {
//	gy := py.parent
//
//	py.right = v.left
//	if v.left != nil {
//		v.left.parent = py
//	}
//
//	v.left = py
//	py.parent = v
//
//	v.sizeLeft += (py.sizeLeft + 1)
//	v.parent = gy
//
//	if py == this.root {
//		this.root = v
//		v.parent = nil
//	} else {
//		if gy.left == py {
//			gy.left = v
//		} else {
//			gy.right = v
//		}
//	}
//}
//
//func (this *DIndexRBTree) rlRotate(py, v, w *RbNode) {
//	gy := py.parent
//
//	v.left = w.right
//	if w.right != nil {
//		w.right.parent = v
//	}
//
//	w.right = v
//	v.parent = w
//
//	py.right = w.left
//	if w.left != nil {
//		w.left.parent = py
//	}
//
//	w.left = py
//	py.parent = w
//
//	v.sizeLeft -= (w.sizeLeft + 1)
//	w.sizeLeft += (py.sizeLeft + 1)
//
//	w.parent = gy
//
//	if py == this.root {
//		this.root = w
//		w.parent = nil
//	} else {
//		if gy.left == py {
//			gy.left = w
//		} else {
//			gy.right = w
//		}
//	}
//
//}
//
//func (this *DIndexRBTree) rllRotate(py, v, w, x *RbNode) {
//	gy := py.parent
//
//	x.color = py.color
//	py.color = BLACK
//
//	w.left = x.right
//	if x.right != nil {
//		x.right.parent = w
//	}
//
//	x.right = v
//	v.parent = x
//
//	py.right = x.left
//	if x.left != nil {
//		x.left.parent = py
//	}
//
//	x.left = py
//	py.parent = x
//
//	w.sizeLeft -= (x.sizeLeft + 1)
//	v.sizeLeft -= (x.sizeLeft + 1)
//	x.sizeLeft += (py.sizeLeft + 1)
//	x.parent = gy
//
//	if py == this.root {
//		this.root = x
//		x.parent = nil
//	} else {
//		if gy.left == py {
//			gy.left = x
//		} else {
//			gy.right = x
//		}
//	}
//}
//
//func (this *DIndexRBTree) rest(k, increase int) {
//	p := this.root
//
//	for p != nil && k != p.data.k {
//		if k < p.data.k {
//			p.sizeLeft += increase
//			p = p.left
//		} else {
//			p = p.right
//		}
//	}
//
//}
//func (this *DIndexRBTree) Insert(k int) {
//    data := NewRbData(k,k)
//	p := this.root
//	var pp *RbNode
//	for p != nil {
//		pp = p
//		if data.k <= p.data.k {
//			p.sizeLeft++
//			p = p.left
//		} else {
//			p = p.right
//		}
//		//fmt.Println(pp.data)
//	}
//
//	newnode := NewRbNode(data, pp, nil, nil)
//	this.size++
//
//	if this.root == nil {
//		newnode.color = BLACK
//		this.root = newnode
//		return
//	}
//
//	if data.k <= pp.data.k {
//		pp.left = newnode
//	} else {
//		pp.right = newnode
//	}
//	this.insertBlanceTree(newnode)
//
//}
//
//func (this *DIndexRBTree) insertBlanceTree(u *RbNode) {
//
//	pu := u.parent
//
//	if pu.color == BLACK {
//		return
//	}
//
//	var gu, uncle *RbNode
//	gu = pu.parent
//
//	var isleft bool
//
//	for pu.color == RED {
//		//fmt.Println(u.data)
//		if gu.left == pu {
//			isleft = true
//			uncle = gu.right
//		} else {
//			isleft = false
//			uncle = gu.left
//		}
//
//		if uncle == nil || uncle.color == BLACK {
//			//一次旋转即可恢复平衡
//			if isleft {
//				if u == pu.left {
//					gu.color = RED
//					pu.color = BLACK
//					this.llRotate(gu, pu)
//				} else {
//					u.color = BLACK
//					gu.color = RED
//					this.lrRotate(gu, pu, u)
//				}
//			} else {
//				if u == pu.right {
//					gu.color = RED
//					pu.color = BLACK
//					this.rrRotate(gu, pu)
//				} else {
//					gu.color = RED
//					u.color = BLACK
//					this.rlRotate(gu, pu, u)
//				}
//			}
//			return
//		}
//		// LLr,LRr,RRr,RLr
//		pu.color = BLACK
//		uncle.color = BLACK
//
//		if gu == this.root {
//			return
//		}
//		gu.color = RED
//
//		u = gu
//		pu = u.parent
//		gu = pu.parent
//
//	}
//
//}
//
//func (this *DIndexRBTree) Delete(k int) {
//	p := this.root
//	for p != nil && k != p.data.k {
//		if k < p.data.k {
//			p.sizeLeft--
//			p = p.left
//		} else {
//			p = p.right
//		}
//	}
//	if p == nil {
//		this.rest(k, 1)
//		return
//	}
//
//	if p.left != nil && p.right != nil {
//
//		d := p.left
//		p.sizeLeft--
//
//		for d.right != nil {
//			d = d.right
//		}
//
//		p.data = d.data
//		p = d
//
//	}
//
//	var n, v *RbNode
//	if p.left != nil {
//		n = p.left
//		n.parent = p.parent
//	} else if p.right != nil {
//		n = p.right
//		n.parent = p.parent
//	} else {
//		n = nil
//	}
//	this.size--
//
//	if p == this.root {
//		this.root = n
//		if n == nil {
//			return
//		}
//		n.parent = nil
//	} else {
//		if p.parent.left == p {
//			p.parent.left = n
//			v = p.parent.right
//
//		} else {
//			p.parent.right = n
//			v = p.parent.left
//		}
//
//	}
//
//	this.deleteBlanceTree(p, n, v)
//
//}
//
//func (this *DIndexRBTree) deleteBlanceTree(p, y, v *RbNode) {
//
//	if p.color == RED || this.root == nil { //平衡未被破坏
//		return
//	}
//
//	if p.color == BLACK && y != nil && y.color == RED {
//		//通过变色y就可简单的恢复平衡
//		y.color = BLACK
//		return
//	}
//
//	py := p.parent
//	//Xb0 变色
//	for v.color == BLACK && (v.left == nil || v.left.color == BLACK) && (v.right == nil || v.right.color == BLACK) {
//		v.color = RED //导致了以y为 根的阶少1所以继续往上
//
//		if py == this.root { //所有路径阶-1
//			return
//		}
//
//		if py.color == RED {
//			py.color = BLACK
//			return
//		}
//
//		y = py
//		py = py.parent
//
//		if y == py.left {
//			v = py.right
//		} else {
//			v = py.left
//		}
//		//fmt.Println(v)
//
//	}
//
//	if v.color == BLACK { //和上面的Xb0一共八种
//		if v == py.left {
//			if (v.left != nil && v.left.color == RED) && (v.right == nil || v.right.color == BLACK) {
//				//Rb1-1
//				v.color = py.color
//				py.color = BLACK
//				v.left.color = BLACK
//				this.llRotate(py, v)
//			} else {
//				//Rb1-2,Rb2
//				w := v.right
//				w.color = py.color
//				py.color = BLACK
//				this.lrRotate(py, v, w)
//			}
//		} else {
//			if (v.right != nil && v.right.color == RED) && (v.left == nil || v.left.color == BLACK) {
//				//Lb1-1
//				v.color = py.color
//				py.color = BLACK
//				v.right.color = BLACK
//				this.rrRotate(py, v)
//			} else {
//				//Lb1-2,Lb2
//				w := v.left
//				w.color = py.color
//				py.color = BLACK
//				this.rlRotate(py, v, w)
//			}
//		}
//	} else { // &&八种
//		if v == py.left {
//			w := v.right
//			if (w.left == nil || w.left.color == BLACK) && (w.right == nil || w.right.color == BLACK) {
//				//Rr0
//				v.color = py.color
//				py.color = BLACK
//				w.color = RED
//				this.llRotate(py, v)
//			} else if (w.left != nil && w.left.color == RED) && (w.right == nil || w.right.color == BLACK) {
//				//Rr1-1
//
//				w.color = py.color
//				py.color = BLACK
//				w.left.color = BLACK
//				this.lrRotate(py, v, w)
//			} else {
//				//Rr1-2 Rr2
//				x := w.right
//				this.lrrRotate(py, v, w, x)
//			}
//		} else {
//			w := v.left
//			//fmt.Println(v.data, p.data)
//			if (w.left == nil || w.left.color == BLACK) && (w.right == nil || w.right.color == BLACK) {
//				v.color = py.color
//				py.color = BLACK
//				w.color = RED
//				this.rrRotate(py, v)
//			} else if (w.right != nil && w.right.color == RED) && (w.left == nil || w.left.color == BLACK) {
//				w.color = py.color
//				py.color = BLACK
//				w.right.color = BLACK
//				this.rlRotate(py, v, w)
//			} else {
//				x := w.left
//				this.rllRotate(py, v, w, x)
//			}
//		}
//
//	}
//
//}
//
//func (this *DIndexRBTree) IndexDelete(i int) {
//	if i > this.size-1 {
//		return
//	}
//	p := this.root
//	index := i
//	for p != nil && index != p.sizeLeft {
//		if index < p.sizeLeft {
//			p.sizeLeft--
//			p = p.left
//		} else {
//			index -= (p.sizeLeft + 1)
//			p = p.right
//		}
//	}
//
//	if p == nil {
//		p = this.root
//		index = i
//		for p != nil {
//			if index < p.sizeLeft {
//				p.sizeLeft++
//				p = p.left
//			} else {
//				index -= (p.sizeLeft + 1)
//				p = p.right
//			}
//		}
//		fmt.Println("=====waht", this.size, i)
//		return
//	}
//
//	this.size--
//
//	if p.left != nil && p.right != nil {
//		d := p.left
//		p.sizeLeft--
//		for d.right != nil {
//			d = d.right
//		}
//		p.data = d.data
//		p = d
//	}
//
//	var n, v *RbNode
//	if p.left != nil {
//		n = p.left
//		n.parent = p.parent
//	} else if p.right != nil {
//		n = p.right
//		n.parent = p.parent
//	} else {
//		n = nil
//	}
//
//	if p == this.root {
//		this.root = n
//	} else {
//		if p.parent.left == p {
//			v = p.parent.right
//			p.parent.left = n
//
//		} else {
//			v = p.parent.left
//			p.parent.right = n
//		}
//
//	}
//
//	this.deleteBlanceTree(p, n, v)
//
//}
//
//
//
//
//type MedianFinder struct {
//    redblackTree *DIndexRBTree
// 
//
//}
//
//
///** initialize your data structure here. */
//func Constructor() MedianFinder {
//
//    return MedianFinder{NewDIndexRBTree()}
//}
//
//
//func (this *MedianFinder) AddNum(num int)  {
//
//    this.redblackTree.Insert(num)
//
//
//
//}
//
//
//func (this *MedianFinder) FindMedian() float64 {
//
//
//    var mid int
//    mid = this.redblackTree.size/2
//    //fmt.Println(this.redblackTree.size)
//    if this.redblackTree.size % 2 == 0 {
//        a := this.redblackTree.IndexSearch(mid-1)
//        b := this.redblackTree.IndexSearch(mid)
//        //fmt.Println(this.redblackTree.size,a,b,mid)
//        return float64((a.k + b.k))/2
//    } 
//    b := this.redblackTree.IndexSearch(mid)
//    //fmt.Println(this.redblackTree.size,b)
//    return float64(b.k)
//    
//
//}
//
//
///**
// * Your MedianFinder object will be instantiated and called as such:
// * obj := Constructor();
// * obj.AddNum(num);
// * param_2 := obj.FindMedian();
// */
//
//
//作者：finin
//链接：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/sha-ye-bu-shuo-liao-zan-men-lai-yi-ge-shou-si-suo-/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
